/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 递归：1. 先序：根左右，中序：左根右
func buildTree(preorder []int, inorder []int) *TreeNode {
	// check nil is very important, 递归出口！！！
	if len(preorder) == 0 {
		return nil
	}

	rootV := preorder[0]
	var index int
	for i, v := range inorder {
		if v == rootV {
			index = i
		}
	}

	root := &TreeNode{
		Val: rootV,
	}
	root.Left = buildTree(preorder[1:1+index], inorder[:index])
	root.Right = buildTree(preorder[1+index:], inorder[index+1:])
	return root
}